5. Forma de examinar de un compilador
En la compilación hay dos partes: Análisis y Síntesis.
La parte del análisis divide al programa fuente
en sus elementos componentes y crea una representación
intermedia. De las dos partes, la síntesis
es la que requiere la técnica más
especializada.
Durante el análisis se determina las operaciones que
implica el programa fuente y
se registra en una estructura
jerárquica llamada árbol. A menudo, se usa una
clase especial de árbol llamado árbol
sintáctico, donde cada nodo representa una
operación y los hijos de un nodo son los argumentos de la
operación. Por ejemplo, en la figura 5 se muestra un
árbol sintáctico para una proposición de
asignación.
Figura 5. Árbol sintáctico para
posición := inicial + velocidad *
60
6. Como se sintetiza el
código
objeto un compilador estándar, teórica y
gráficamente generación de
código
En esta parte el código
intermedio optimizado es traducido a una secuencia de
instrucciones en ensamblador o
en el código de máquina del procesador que
nos interese. Por ejemplo, la sentencia
A:=B+C se convertirá en:
LOAD B
ADD C
STORE A
suponiendo que estas instrucciones existan de esta forma en el
ordenador de que se trate. Una conversión tan directa
produce generalmente un programa objeto que contiene muchas
cargas (loads) y almacenamientos (stores) redundantes, y que
utiliza los recursos de la
máquina de forma ineficiente. Existen técnicas
para mejorar esto, pero son complejas. Una, por ejemplo, es
tratar de utilizar al máximo los registros de
acceso rápido que tenga la máquina. Así, en
el procesador 8086
tenemos los registros
internos AX, BX, CX, DX, etc. y podemos utilizarlos en vez de
direcciones de memoria.
Tabla De Símbolos
Un compilador necesita guardar y usar la información de los objetos que se va
encontrando en el texto fuente,
como variables,
etiquetas, declaraciones de tipos, etc. Esta información se almacena en una estructura de
datos interna conocida como tabla de símbolos. El
compilador debe desarrollar una serie de funciones
relativas a la manipulación de esta tabla como insertar un
nuevo elemento en ella, consultar la información
relacionada con un símbolo, borrar un elemento, etc. Como
se tiene que acceder mucho a la tabla de símbolos los
accesos deben ser lo más rápidos posible para que
la compilación sea eficiente.
Manejo de errores
Es una de las misiones más importantes de un compilador,
aunque, al mismo tiempo, es lo que
más dificulta su realización. Donde más se
utiliza es en las etapas de análisis sintáctico y
semántico, aunque los errores se pueden descubrir en
cualquier fase de un compilador. Es una tarea difícil, por
dos motivos:
- A veces unos errores ocultan otros.
- A veces un error provoca una avalancha de muchos
errores que se solucionan con el primero.
Es conveniente un buen manejo de errores, y que el
compilador detecte todos los errores que tiene el programa y no
se pare en el primero que encuentre. Hay, pues, dos criterios a
seguir a la hora de manejar errores:
- Pararse al detectar el primer error.
- Detectar todos los errores de una
pasada.
En el caso de un compilador interactivo (dentro de un
entorno de desarrollo
integrado, como Turbo-Pascal o Borland
C++) no importa que se pare en el primer error detectado, debido
a la rapidez y facilidad para la corrección de
errores.
7. Árboles
sintácticos para representar como sintetiza el
código objeto un compilador
Figura 6.- Generación de
código.
figura 7.- Código en ensamblador
para la figura 6.
8. Herramientas
que muestran tipos de análisis de programas
fuente
Muchas herramientas
de software que
manipulan porgraas fuente realizan primero algún tipo de
análisis. Algunos ejemplos de tales herramientas
son:
- Editores de estructuras: un editor de estructuras toma como entrada uan secuencia de
ordenes para construir un programa fuente. El editor de
estructuras no sólo realiza las funciones de
creación y modificación de textos de un editor
de textos ordinario, sino que también analiza el
texto del
programa imponiendo al programa fuente una estructura
jerárquica apropiada. De esa manera, el editor de
estructuras puede realizar tareas adicionales útiles
para la preparación de programas.
Por ejemplo, puede comprobar si la entrada está
formada correctamente, puede proporcionar palabras clave de
manera automática y puede saltar desde un begin o un
paréntesis izquierdo hasta su correspondiente end o
paréntesis derecho. Además, la salida de tal
editor suele ser similar a la salida de la fase del
análisis de un compilador. - Impresoras estéticas: Una impresora
estética analiza un programa y lo
imprime de forma que la estructura del programa resulte
claramente visible. Por ejemplo, los comentarios pueden
aparecer con un tipo de letra especial, y las proposiciones
pueden aparecer con una indentación proporcional a la
profundidad de su anidamiento en la
organización jerárquica de las
proposiciones. - Verificadores estáticos: Un verificador
estático lee un programa, lo analiza e intenta
descubrir errores potenciales sin ejecutar el programa. La
parte del análisis es similar a la que se encuentra en
los compiladores de optimación. Así
un verificador estático puede detectar si hay partes
de un programa que nunca se podrán ejecutar o si
cierta variable se usa antes de ser definida. Además,
puede detectar errores de lógica como intentar utilizar una
variable real como apuntador, empleando las técnicas de verificación de
tipos. - Intérpretes: En lugar de producir un
programa objeto como resultado de una traducción, un
interprete realiza las operaciones
que implica el programa fuente. Para una proposición
de asignación, por ejemplo, un intérprete
podría construir un árbol como el de la figura
5, y después efectuar las operaciones de los nodos
conforme "recorre" el árbol. En la raíz
descubriría que tiene que realizar una
asignación, y llamaría a una rutina para
evaluar la expresión de la derecha y después
almacenaría el valor
resultante en la localidad de memoria
asignada con el identificador posición. En el hijo
derecho de la raíz, la rutina descubriría que
tiene que calcular la suma de dos expresiones. Se
llamaría a si misma de manera recursiva para calcular
el valor de
la variable inicial.
9. Diagrama de
análisis de un programa fuente, definiendo cada una de sus
partes
Al principio de la historia de los compiladores, el
tamaño del programa ejecutable era un recurso
crítico, así como la memoria que
utilizaba el compilador para sus datos, por lo que
lo frecuente era que cada fase leyera un fichero escrito por la
fase anterior y produjera un nuevo fichero con el resultado de
las transformaciones realizadas en dicha fase. Esta
técnica (inevitable en aquellos tiempos) hacía que
el compilador realizara muchas pasadas sobre el programa fuente.
En los últimos años el tamaño del fichero
ejecutable de un compilador es relativamente pequeño
comparado con el de otros programas del sistema, y
además (gracias a los sistemas de
memoria
virtual) normalmente no tienen problemas de
memoria para compilar un programa medio. Por estos motivos, y
dado que escribir y leer un fichero de tamaño similar o
mayor que el del programa fuente en cada fase es una
pérdida considerable de tiempo (incluso
en los sistemas
modernos), la tendencia actual es la de reducir el número
de ficheros que se leen o escriben y por tanto reducir el
número de pasadas, incluso el de aquéllas que se
realizan en memoria, sin escribir ni leer nada del disco.
Las fases se agrupan en dos partes o etapas: front end (las fases
de análisis) y back end (las fases de generación y
optimización de código). Estas dos etapas se
comunican mediante una representación intermedia (generada
por el front end), que puede ser una representación de la
sintaxis del programa (un árbol sintáctico
abstracto) o bien puede ser un programa en un lenguaje
intermedio. El front end depende del lenguaje
fuente y casi siempre es independiente (o debe serlo) de la
máquina objeto para la que se va a generar código;
el back end depende del lenguaje objeto y debe ser independiente
del lenguaje fuente (excepto quizá para algún tipo
de optimización).
Análisis Léxico
El analizador léxico, también conocido como
scanner, lee
los caracteres uno a uno desde la entrada y va formando grupos de
caracteres con alguna relación entre sí (tokens),
que constituirán la entrada para la siguiente etapa del
compilador. Cada token representa una secuencia de caracteres que
son tratados como una
única entidad. Por ejemplo, en Pascal un token
es la palabra reservada BEGIN, en C: WHILE, etc.
Hay dos tipos de tokens: tiras específicas, tales como
palabras reservadas (if, while, begin, etc.), el punto y coma, la
asignación, los operadores aritméticos o
lógicos, etc.; tiras no específicas, como
identificadores, constantes o etiquetas. Se considera que un
token tiene dos partes componentes: el tipo de token y su valor.
Las tiras específicas sólo tienen tipo (lo que
representan), mientras que las tiras no específicas tienen
tipo y valor. Por ejemplo, si "Contador" es un identificador, el
tipo de token será identificador y su valor será la
cadena "Contador".
El Analizador Léxico es la etapa del compilador que va a
permitir saber si es un lenguaje de formato libre o no.
Frecuentemente va unido al analizador sintáctico en la
misma pasada, funcionando entonces como una subrutina de este
último. Ya que es el que va leyendo los caracteres del
programa, ignorará aquellos elementos innecesarios para la
siguiente fase, como los tabuladores, comentarios, espacios en
blanco, etc.
Figura 8.- Análisis léxico.
Análisis Sintáctico
El analizador sintáctico, también llamado parser,
recibe como entrada los tokens que le pasa el Analizador
Léxico (el analizador sintáctico no maneja
directamente caracteres) y comprueba si esos tokens van llegando
en el orden correcto (orden permitido por el lenguaje).
La salida "teórica" de la fase de análisis
sintáctico sería un árbol
sintáctico.
Así pues, sus funciones son:
- Aceptar lo que es válido
sintácticamente y rechazar lo que no lo es. - Hacer explícito el orden jerárquico que
tienen los operadores en el lenguaje
de que se trate. Por ejemplo, la cadena A/B*C es interpretada
como (A/B)*C en FORTRAN y comoA/(B*C) en APL. - Guiar el proceso de
traducción (traducción dirigida por la
sintaxis).
Análisis Semántico
El análisis semántico es posterior al
sintáctico y mucho más difícil de formalizar
que éste. Se trata de determinar el tipo de los resultados
intermedios, comprobar que los argumentos que tiene un operador
pertenecen al conjunto de los operadores posibles, y si son
compatibles entre sí, etc. En definitiva,
comprobará que el significado de lo que se va leyendo es
válido.
La salida "teórica" de la fase de análisis
semántico sería un árbol semántico.
Consiste en un árbol sintáctico en el que cada una
de sus ramas ha adquirido el significado que debe tener. En el
caso de los operadores polimórficos (un único
símbolo con varios significados), el análisis
semántico determina cuál es el aplicable. Por
ejemplo, consideremos la siguiente sentencia de
asignación:
A := B + C
En Pascal, el signo "+" sirve para sumar enteros y reales,
concatenar cadenas de caracteres y unir conjuntos. El
análisis semántico debe comprobar que B y C sean de
un tipo común o compatible y que se les pueda aplicar
dicho operador. Si B y C son enteros o reales los sumará,
si son cadenas las concatenará y si son conjuntos
calculará su unión.
Ejemplo
VAR
ch : CHAR; (* Un identificador no se puede utilizar si *)
ent: INTEGER; (* previamente no se ha definido. *)
…
ch := ent + 1; (* En Pascal no es válido, en C sí.
*)
Análisis Léxico: Devuelve la secuencia de
tokens: id asig id suma numero ptocoma
Análisis Sintáctico: Orden de los tokens
válido
Análisis Semántico: Tipo de variables
asignadas incorrecta
Estructura del programa fuente
Programa fuente
Programa objeto en lenguaje ensamblador
Código de máquina relocalizable
Código de máquina absoluto
Figura 9.- Sistema para
procesamiento de un lenguaje
Figura 10.- Árbol de análisis
sintáctico para posición := inicial + velocidad *
60.
Este trabajo servirá mucho en el momento de la
creación de un compilador, ya que en él se detallan
todas y cada una de las partes que involucran a este.
Primeramente investigue que existen distintos tipos de
compiladores, me gustaria crear un compilador de
optimación, ya que pienso que es muy útil a la hora
de crear un algoritmo o
programa. La función de
un compiladores es leer un programa escrito es un lenguaje, en
este caso el lenguaje fuente, y lo traduce a un programa
equivalente en otro lenguaje, el lenguaje objeto. Me parece
fascinante que nosotros podamos crear un compilador en seis meses
(en un curso), cuando en los años 50, ya que en aquellos
tiempos se tardaron hasta 18 años trabajando en un
compilador.
Por otro lado, comprendí que un compilador, requiere de
una sintaxis y lenguajes específicos, ya que, al igual que
el lenguaje humano, si no lo escribimos correctamente el
compilador no hará lo que deseamos. Y que en la
compilación hay dos partes: Análisis y
Síntesis. La parte del análisis divide al programa
fuente en sus elementos componentes y crea una
representación intermedia.
Aprendí que las herramientas que muestran tipos de
análisis de programas fuente, son muy útiles al
momento de crear un programa al codificar un algoritmo, ya
que estas herramientas nos ayudan formateando el texto,
corrigiendo errores, dando tips; para que nosotros como
programadores seamos más eficientes al momento de crear
alguna aplicación.
También he notado como todas nuestras materias se va
complementando y enlazando, por ejemplo, en matemáticas discretas vimos la
representación de árboles, los cuales usamos aquí.
Igualmente en estructura de
datos I, vimos métodos de
ordenamiento que las gramáticas de los compiladores usan.
Por lo tanto, no parece tan complicado crear un compilador,
sólo se necesitan los conocimientos adecuados y dedicarle
su tiempo para tener éxito.
- Compiladores, Principios,
técnicas y herramientas, Alfred V. Aho, Ravi Sethi,
Jeffrey D. Ullman. Addison – Wesley
iberoamericana. - http://www.dlsi.ua.es/docencia/asignaturas/comp1/comp1.html
- http://www.cps.unizar.es/~ezpeleta/COMPI
- http://www.ii.uam.es/~alfonsec
- Compiladores: Conceptos Fundamentales. B. Teufel, S.
Schmidt, T. Teufel. Addison Wesley Iberoamericana.
Ceballos Carmona Miguel Ángel, 25 años
Estudiante universitario del ITESI, en Irapuato, Gto.
Trabajo para la materia
Lenguajes y autómatas. Creado en Febrero del 2002.
Palabras clave para Búsqueda: compiladores, lenguajes y
autómatas, análisis léxico, análisis
sintáctico, análisis semántico,
árboles sintácticos, Compilador cruzado, Compilador
con montador, autocompilador, metacompilador, descompilador,
código objeto.
Autor:
Miguel Ángel
 Página anterior | Volver al principio del trabajo | Página siguiente  |